iT邦幫忙

4

用Javascript征服演算法 (4-insertion sort&實作)

  • 分享至 

  • xImage
  •  

來來來,各位看官今天是insertion sort囉~
在Selection Sort的部分我們已經講解使用selection sort會如何去對一串未排序的數列作排序的動作,那今天就要來介紹另外一個基本的sort

insertion sort哈哈 笑屁 (歐飛

在此復習一下selection sort,selection sort的方式是去選擇最大or最小值,然後加入已排序的集合最後面,也就表示,一開始就必須要從未排序集合中去尋找最小值or最大值的動作,也就是先做compare後,就可直接加入已排序最後面

而insertion sort不同的地方在於,每次選擇未排序集合最前端的值,然後加入已排序集合中適當的位置,而所謂的適當的位置,也就是需要去做compare的動作,也就是說,先直接選擇未排序中最前面的值,再去做compare的動作,放入已排序的集合中(如下圖顯示兩者之不同)

在瞭解insertion sort的做法後,就來試試看用Javascript實作出來吧
在此先依照由大到小排序
好的,首先呢當然是先寫出第一個function,將陣列值取出來方便後續處理

function insertionSort(list) {
for(var i = 0; i < list.length; i++) {
   //在此就可以將陣列list及每一個值丟進另外一個處理compare的function作處理

}

接下來是在已排序的集合中,去找出適當的位置來插入,而適當的位置應該就是找出已排序集合中是否有值比自己小(就代表自己比較大應該排在他前面),如果有,就必須要做插入的動作,如果沒有,就可以不需要動

//return i表示為比自己小到list的哪一個位置
//如果沒有比自己小的,就會跑到i = elementIdx,那return的就是自己的位置
function insertedIdx(list, elementIdx) {
//搜尋已排序集合
for(var i = 0; i < elementIdx; i++) {
    if(list[i] < list[elementIdx]) { break; }
}
return i;
}

找到i後,就可以開始做插入的動作,而原本是要做出插入至比自己小的數值前面,也就是說,先將原本在那位置及在它後面的元素往後退一位後,空出來的位置,就是是把自己插入的位置了

function insert(list,elementIdx ,insertedIdx){
    var tmp = list[elementIdx];

    for(var i = elementIdx; i > inserted; i--)
    {
        list[i] = list[i-1];

    } 
   list[insertedIdx] = tmp; 

}

大公告成><,在把寫完的function在第一個function中完成呼叫動作即可~飛

function insertionSort(list) {
for(var i = 0; i &lt; list.length; i++) {
    var inserted = insertedIdx(list, i);

    if(inserted !== i) { insert(list, i, inserted); }
 }    
}

以下是完整的程式碼~請參考之~~

//尋找要插入的位置
function insertedIdx(list, elementIdx) {
//搜尋已排序集合
for(var i = 0; i &lt; elementIdx; i++) {
    if(list[i] &lt; list[elementIdx]) { break; }
}
return i;
}
//插入至
function insert(list, elementIdx, inserted) {
    var tmp = list[elementIdx];

    for(var i = elementIdx; i > inserted; i--)
    {
        list[i] = list[i-1];

    }  
list[inserted] = tmp;
console.log(list[inserted]);
}

function insertionSort(list) {
    for(var i = 0; i &lt; list.length; i++) {
        var inserted = insertedIdx(list, i);
        //如果不是原本那位置的話,代表需要做插入動作
    if(inserted !== i) { insert(list, i, inserted); }
    }    
}
var list = [10, 9, 1, 2, 5, 3, 8, 7];
insertionSort(list);
alert(list);

可執行的jsfiddle在此~
http://jsfiddle.net/stanney/UsTee/1/

下一個就是可愛的小賴大大喜歡的可愛的bubble sort囉~開心


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言